Number of 1 Bits

LeetCode 191 | Difficulty: Easy

Easy

Problem Description

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

- `1 <= n <= 2^31 - 1`

Follow up: If this function is called many times, how would you optimize it?

Topics: Divide and Conquer, Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 56 ms)

Metric	Value
Runtime	56 ms
Memory	N/A
Date	2017-12-28

Solution

public class Solution {
    public int HammingWeight(uint n) {
        int count = 0;
        while(n!=0)
        {
            n &= n-1;
            count++;
        }
        return count;
    }
}

📜 1 more C# submission(s)

Submission (2017-12-28) — 82 ms, N/A

public class Solution {
    public int HammingWeight(uint n) {
        if(n==0) return 0;
        int count = 0;
        while(n!=0)
        {
            n &= n-1;
            count++;
        }
        return count;
    }
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.